CSE 311: Section 2

Task 1 – Simple Formal Proofs

1. Given $(a \to b$), $(c \to b)$, $a \lor (c \land d)$, show that $b$ holds.

2. Given $\neg(\neg r \vee k)$, $\neg q \vee \neg s$ and $(p\to q) \wedge (r\to s)$, show that $\neg p$ holds.

Task 2 – Direct Proofs

1. Show that $\neg k \to s$ follows from $k\vee q$, $q\to r$ and $r\to s$ with a formal proof.

2. Show that $r \to p$ follows from $p \vee \neg q$, $(r \vee s) \to (q \vee s)$, and $\neg s$.

Task 3 – Predicate Logic Proofs

1. Given $\forall x\, (T(x) \rightarrow M(x))$, prove $(\exists x\, T(x)) \rightarrow (\exists y\, M(y))$.

2. Given $\exists x\, (T(x) \rightarrow \forall y\, S(y, x))$, prove $\forall y\, \exists x\, (T(x) \rightarrow S(y, x))$.

Task 4 – English Proofs

Let domain of discourse be the integers. Consider the following claim: $$\forall x\, \forall y\, ((\mathop{\mathrm{\textsf{Even}}}(x) \wedge \mathop{\mathrm{\textsf{Odd}}}(y)) \to \mathop{\mathrm{\textsf{Odd}}}(x+y))$$ In English, this says that, for any even integer $x$ and odd integer $y$, the integer $x + y$ is odd.

1. Write a formal proof that the claim holds.

2. Translate your formal proof to an English proof.

   Keep in mind that your proof will be read by a human, not a computer, so you should explain the algebra steps in more detail, whereas some of the predicate logic steps (e.g., Elim $\exists$) can be skipped.